// 快速排序 https://blog.csdn.net/rxbook/article/details/130944808
package main

import "fmt"

func QuickSort(arr []int) {
	arrLen := len(arr)
	if arrLen <= 1 {
		return
	}
	quickSort(arr, 0, arrLen-1)
}

func quickSort(arr []int, start, end int) {
	if start >= end {
		return
	}

	Q := partition(arr, start, end)
	quickSort(arr, start, Q)
	quickSort(arr, Q+1, end)
}

// 分区函数,随机选择一个元素作为Q（一般情况下，可以选择起点到结尾区间的最后一个元素），返回Q的下标。
func partition(arr []int, low, high int) int {
	Q := arr[low]
	for low < high {
		//指针从右边开始向右找到一个比Q小的数
		for low < high && arr[high] > Q {
			high--
		}
		//将这个数放到low位，注意第一次这个位置放的是Q值，所以不会丢
		arr[low] = arr[high]
		//指针从左边开始向右找到第一个比Q大的数
		for low < high && arr[low] < Q {
			low++
		}
		//将这个数赋值给之前的high指针，因为之前high指针指向的数已经被一定，所以不会丢
		arr[high] = arr[low]
	}
	//最后将Q的值放入合适位置，此时low与high相等
	arr[low] = Q
	return low
}

func main() {
	arr := []int{8, 4, 5, 7, 1, 3, 6, 2}
	QuickSort(arr)
	fmt.Println(arr) //[1 2 3 4 5 6 7 8]
}
